There are many systems where a communication channel is shared amongst a plurality of processing elements, with the various processing elements issuing messages over the communication channel to recipient elements. The communication channel may take the form of bus interconnect circuitry used to connect a number of master devices with a number of slave devices within a chip such as a System-on-Chip (SoC) device, or to connect individual chips in a multi-chip module, or indeed to interconnect various modules within a printed circuit board structure. On a larger scale, the communication channel may be formed by a network interconnecting a plurality of computers, or a shared radio link used to interconnect a plurality of devices.
For any communication channel, there is a limit to the information carrying capacity of that channel, and there is also a latency associated with the communication channel. There are architectural options which enable the channel capacity and latency to be varied, such as the use of parallelisation techniques and increased operating frequency. However, such techniques have a cost in complexity, power and area which need to be traded against the required performance.
In any system where a communication channel is shared amongst a plurality of processing elements, with those processing elements needing to issue messages over the communication channel when executing a process, the fact that the communication channel is shared forces decisions to be made regarding the order in which the messages are processed through the communication channel, and this decision is made by employing arbitration techniques. Considering the example of a SoC, the messages may take the form of signals issued by a master device during a transaction, and in particular the master device will typically initiate a transaction by issuing an access request onto the communication channel specifying a slave device associated with the transaction. It is known in this particular field that certain ordering of transactions will result in a lower total latency than other orderings, and this is an area where devices such as memory controllers often specialise. However, the arbitration decision will necessarily add to the latency experienced by the process whose message has been held back as a result of the arbitration decision. Accordingly, the way in which this arbitration decision is made will have a significant effect on the overall performance of the system.
Basic arbitration schemes use algorithms that employ fixed priority or round robin (fair share) techniques. Such schemes are limited to making the arbitration decision on a message-by-message basis and take limited account of choices made in the past. The exception with the round robin scheme is that the current priority depends on the previous priorities. However, both schemes suffer from the problem that they allocate the additional latency introduced through the communication channel on a message-by-message basis rather than between the individual processes issuing the messages. Consequently, a message that has high levels of access through the communication channel will receive high levels of additional latency over time as a result of the arbitration decisions made within the communication channel.
An alternative technique which has been developed primarily for networks is the Quality-of-Service (QoS) technique, which takes a time based view by attempting to ensure that a process has a required bandwidth and controlled latency characteristics. Hence, such QoS schemes consider each process and allocate a proportion of the bandwidth of the communication channel to that process with some control over the latency applied to each transaction or message. However, the limitation with known QoS schemes is that the characteristics of each process are assumed to be known prior to the actual data flow occurring when those processes are executed, and also require some higher level protocol to manage that information. Hence, such QoS schemes are inflexible to changes in the bandwidth or latency characteristics, require the characteristics to be known in advance, and require a higher level protocol to configure the operation of the communication channel to provide the necessary characteristics to the processes. Hence, existing QoS schemes start from the assumption that the communication channel offers performance, and allocate this performance according to predefined requirements from the processes. This can lead to processes that have lower bandwidth requirements than anticipated getting an unfair performance, while other processes that exceed their predefined characteristics are starved of performance.
Whilst some of these known QoS schemes can work acceptably within a network environment, in other types of systems, for example a SoC, the data flows occurring through the shared communication channel can be random (e.g. resulting from cache misses and the like) and dynamically variable, and thus as such are not suitable for existing QoS schemes.
Accordingly, it would be desirable to provide an improved technique for arbitrating between messages routed over a shared communication channel.